////https://www.luogu.com.cn/problem/P2858
//
//#include<iostream>
//
//using namespace std;
//
//const int N = 2010;
//int dp[N][N];
//int x[N];
//
//int main()
//{
//	int n; cin >> n;
//	for (int i = 1; i <= n; i++)
//		cin >> x[i];
//	for (int len = 1; len <= n; len++)
//	{
//		for (int l = 1; l + len - 1 <= n; l++)
//		{
//			int r = l + len - 1;
//			int day = n - len + 1;
//			dp[l][r] = max(dp[l + 1][r] + day * x[l], dp[l][r - 1] + day * x[r]);
//		}
//	}
//	cout << dp[1][n] << endl;
//	return 0;
//}